在上篇文章RSA加密(二)中我们介绍了RSA加密的过程，并留下了三个问题：
遗留问题：
- RSA在公钥和密文传输的过程中就真的很安全吗？
- 为什么解密的时候原文：m 就等于 $c^d$ % n呢？
- m<n，这就导致RSA加密的内容长度受到了限制，那如何加密发送一段很长的文本呢？
在分析安全性之前，我们先简短的回顾下加解密过程：
简单回顾
1.生成共钥、私钥
- 找出质数p、q，p≠q.
- 计算n = p x q.
- 计算n的欧拉函数φ(n)=(p-1)(q-1)
- 选取整数e，条件是1< e < φ(n)，且e与φ(n) 互质，则公钥为:（e,n)
- 计算e对于φ(n)的模反元素d，将d和当作私钥:（d,n)
2.加密、解密
- 加密：用公钥对信息m加密，计算密文：c = $m^e$ % n.
- 解密：用私钥对密文c解密，计算原文：m = $c^d$ % n.
参考上面的加密过程，我们先来看看RSA加密的安全性。
安全性
说到安全性，首先我们想到的就是如何破解，首先在传输过程中被暴露的信息如下：
公钥:（e,n) 、 密文：c
先来看下解密公式：m = $c^d$ % n，想要得到信息m，就得知道c、d和n，对比上面截获的内容，c和n都已知，只有d我们不知道，查看上面生成公私钥步骤5，d是e对于φ(n)的模反元素，即有：
ed % φ(n) = 1
e在公钥中我们已知，要求d，所以求出φ(n)就行，那φ(n)又怎么求呢？通过上面生成共私钥步骤3：
φ(n)=(p-1)(q-1)
所以问题变成了，我们只需要求出p和q就可以了，那p和q又怎么求呢，通过上面生成共私钥步骤2：
n = p x q
n在公钥中我们已知，只需要分解n就可以，但在实际应用中，n一般取1024位或更大的2048位，在第一篇文章中我们知道分解大数的质因数是当今三大数学难题之一，所以RSA加密在理论上是安全的。当今人类被报道破解的最大密钥长度是768位，232个十进制数，写下来如下:
一般认为1024位的密钥基本安全，长度为2048位的密钥极其安全。就拿上述整数来说大小为$10^{232}$来暴力破解，用当今最快的超级计算机美国Summit，计算速度达到每秒200petaflops（千万亿次）即每秒$2*10^{17}$次，加上高效的质因数分解算法Pollard Rho算法 (时间复杂度为$O(n^{\frac14})$，计算下来也需要大概 $10^{33}$ 年，(当然实际破解中会用到很多方法大幅降低破解难度)，所以在当下计算质因数分解没有实质性理论突破的时代，只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。
解密原理
根据上面的加解密过程：加密：c = $m^e$ % n ，这个过程好理解，几个参数都是计算好的，没什么不好理解，我们来看下解密公式：
$c^d$ % n = m
为什么计算的结果就是原文呢？下面我们来证明下上面的解密公式：
- 根据加密公式，可转换为c = $m^e-kn$.
- 将上式带入解密公式 m = $c^d$ % n 得到： $(m^e-kn)^d$ % n = m.
- 因为$(m^e-kn)^d$ 中第二项含有kn是n的倍数，所以不管d是多少，乘开后，只有$m^{ed}$项不含有n，而含有n的项都能被n整除，所以上式可以简化成 $m^{ed}$ % n = m.
- 上面加密过程第5步求模反元素公式： ed % φ(n) = 1，可写成 ed = hφ(n)+1，将其带入$m^{ed}$ % n = m
即证明：$m^{hφ(n)+1}$ % n = m 或 $m^{ed}$ % n = m.
下面我们分两种情况来证明：
- m、n互质
- 由欧拉定理可知 $m^{φ(n)}$%n = 1.
- 上式可变为：$ (m^{φ(n)})^h$ % n = 1，例如$5^1$%4=1、$5^2$%4=1、$5^3$%4=1…
- $ (m^{φ(n)})^h$ % n = 1 等价于 $m^{hφ(n)}$ % n = 1，可写成$m·m^{hφ(n)}$ % n = m，例如5%4=1、2·5%4=2、3·5%4=3、4·5%4=4
- $m·m^{hφ(n)}$ % n = m 可写成 $m^{hφ(n)+1}$ % n = m，原式得证！
- m、n不互质
- 由加密过程：n = p x q，故n只能被分解成p和q的乘积，因为m和n不互质，故m一定是p或q的倍数，以m=kp为例，此时kp和q互质。
- 根据欧拉定理有：$(kp)^{φ(q)}$ % q = 1即：$ (kp)^{q-1} $ % q = 1.
- 上式进行h(p-1)次方运算再乘kp后得到：$[ (kp)^{q-1}]^{h(p-1)} $ x kp % q = kp，左边合并指数后得到：$(kp)^{h(p-1)(q-1)+1} $ % q = kp.
- 从上面我们已知 ed = hφ(n)+1即ed =h(p-1)(q-1)+1，所以上式可简化成：$(kp)^{ed}$ % q = kp.
- 上式可写成$(kp)^{ed}$ = tq + kp，可以发现，等式左边肯定是p的倍数，右边kp是p的倍数，所以tq也是p的倍数，而p和q互质，所以t一定能被p整除，即一定有 t =t’p，带入可得：$(kp)^{ed}$ = t’pq + kp.
- 从上面可知m=kp、n=pq，所以带入上式得: $m^{ed}$ = t’n + m，即：$m^{ed}$ % n = m，原式得证！
可以看到在证明解密公式的过程中，我们频繁用到了欧拉函数和欧拉定理，如果没有欧拉函数和欧拉定理也不会有RSA算法的出现，可见理论数学的重要性！
加密长度限制
我们再来看第一个问题，由于生成随机的大质数p和q也是需要算法的，当n的长度为8192位时，通过macbook pro实测生成密钥时间在5秒以上，效率直线下降。这样就导致n不能太大，所以加密的文本也不能太长，一般来讲我们有如下两种方式来解决这个问题：
- 分段加密：即可以通过将发送的消息分成多段，分别加密，再进行传输。
- 结合AES加密：可通过对称性加密算法AES对长文本进行快速加密，再通过RSA加密算法对AES加密的密钥进行加密。
第二种方式，只有破解加密后的密钥才能解密原文，但要破解加密后的密钥，相当于破解RSA加密，所以这种方式很好的解决了长文本加密的问题，并在实际开发中得到了广泛的应用。
展望
到这里RSA加密系列的文章就结束了，我们从密码学的发展，引出了非对称性加密，从而带大家认识了RSA加密的过程，最后剖析了RSA加密的原理，从而更深层次的了解到了RSA加密的安全性。但随着量子加密的提出，尤其是秀尔算法的提出，RSA加密在量子计算机普及后将变得不再安全，相信到那时密码学必会有革命性的变化。